lib/Mi manual de algoritmos/version_maraton_interuniversitaria_2008-2/src/grafos/dijkstra.tex

   1 % Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
   2
   3 {\ttfamily \raggedright {
   4 \noindent
   5 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$iostream$>$}} \\
   6 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$algorithm$>$}} \\
   7 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$queue$>$}} \\
   8 \mbox{} \\
   9 \mbox{}\textbf{\textcolor{Blue}{using}}\ \textbf{\textcolor{Blue}{namespace}}\ std\textcolor{BrickRed}{;} \\
  10 \mbox{} \\
  11 \mbox{}\textbf{\textcolor{Blue}{struct}}\ edge\textcolor{Red}{\{} \\
  12 \mbox{}\ \ \textcolor{ForestGreen}{int}\ to\textcolor{BrickRed}{,}\ weight\textcolor{BrickRed}{;} \\
  13 \mbox{}\ \ \textbf{\textcolor{Black}{edge}}\textcolor{BrickRed}{()}\ \textcolor{Red}{\{\}} \\
  14 \mbox{}\ \ \textbf{\textcolor{Black}{edge}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ t\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ w\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{:}\ \textbf{\textcolor{Black}{to}}\textcolor{BrickRed}{(}t\textcolor{BrickRed}{),}\ \textbf{\textcolor{Black}{weight}}\textcolor{BrickRed}{(}w\textcolor{BrickRed}{)}\ \textcolor{Red}{\{\}} \\
  15 \mbox{}\ \ \textcolor{ForestGreen}{bool}\ \textbf{\textcolor{Blue}{operator}}\ \textcolor{BrickRed}{$<$}\ \textcolor{BrickRed}{(}\textbf{\textcolor{Blue}{const}}\ edge\ \textcolor{BrickRed}{\&}that\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{const}}\ \textcolor{Red}{\{} \\
  16 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{return}}\ weight\ \textcolor{BrickRed}{$>$}\ that\textcolor{BrickRed}{.}weight\textcolor{BrickRed}{;} \\
  17 \mbox{}\ \ \textcolor{Red}{\}} \\
  18 \mbox{}\textcolor{Red}{\}}\textcolor{BrickRed}{;} \\
  19 \mbox{} \\
  20 \mbox{}\textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{main}}\textcolor{BrickRed}{()}\textcolor{Red}{\{} \\
  21 \mbox{}\ \ \textcolor{ForestGreen}{int}\ N\textcolor{BrickRed}{,}\ C\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  22 \mbox{}\ \ \textbf{\textcolor{Black}{scanf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}\%d"{}}}\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{\&}N\textcolor{BrickRed}{);} \\
  23 \mbox{}\ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}N\textcolor{BrickRed}{-\/-}\ \textcolor{BrickRed}{\&\&}\ \textcolor{BrickRed}{++}C\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  24 \mbox{}\ \ \ \ \textcolor{ForestGreen}{int}\ n\textcolor{BrickRed}{,}\ m\textcolor{BrickRed}{,}\ s\textcolor{BrickRed}{,}\ t\textcolor{BrickRed}{;} \\
  25 \mbox{}\ \ \ \ \textbf{\textcolor{Black}{scanf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}\%d\ \%d\ \%d\ \%d"{}}}\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{\&}n\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{\&}m\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{\&}s\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{\&}t\textcolor{BrickRed}{);} \\
  26 \mbox{}\ \ \ \ vector\textcolor{BrickRed}{$<$}edge\textcolor{BrickRed}{$>$}\ g\textcolor{BrickRed}{[}n\textcolor{BrickRed}{];} \\
  27 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}m\textcolor{BrickRed}{-\/-)}\textcolor{Red}{\{} \\
  28 \mbox{}\ \ \ \ \ \ \textcolor{ForestGreen}{int}\ u\textcolor{BrickRed}{,}\ v\textcolor{BrickRed}{,}\ w\textcolor{BrickRed}{;} \\
  29 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Black}{scanf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}\%d\ \%d\ \%d"{}}}\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{\&}u\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{\&}v\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{\&}w\textcolor{BrickRed}{);} \\
  30 \mbox{}\ \ \ \ \ \ g\textcolor{BrickRed}{[}u\textcolor{BrickRed}{].}\textbf{\textcolor{Black}{push$\_$back}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{edge}}\textcolor{BrickRed}{(}v\textcolor{BrickRed}{,}\ w\textcolor{BrickRed}{));} \\
  31 \mbox{}\ \ \ \ \ \ g\textcolor{BrickRed}{[}v\textcolor{BrickRed}{].}\textbf{\textcolor{Black}{push$\_$back}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{edge}}\textcolor{BrickRed}{(}u\textcolor{BrickRed}{,}\ w\textcolor{BrickRed}{));} \\
  32 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  33 \mbox{} \\
  34 \mbox{}\ \ \ \ \textcolor{ForestGreen}{int}\ d\textcolor{BrickRed}{[}n\textcolor{BrickRed}{];} \\
  35 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}n\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\ d\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ INT$\_$MAX\textcolor{BrickRed}{;} \\
  36 \mbox{}\ \ \ \ d\textcolor{BrickRed}{[}s\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  37 \mbox{}\ \ \ \ priority$\_$queue\textcolor{BrickRed}{$<$}edge\textcolor{BrickRed}{$>$}\ q\textcolor{BrickRed}{;} \\
  38 \mbox{}\ \ \ \ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{push}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{edge}}\textcolor{BrickRed}{(}s\textcolor{BrickRed}{,}\ \textcolor{Purple}{0}\textcolor{BrickRed}{));} \\
  39 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{empty}}\textcolor{BrickRed}{()}\ \textcolor{BrickRed}{==}\ \textbf{\textcolor{Blue}{false}}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  40 \mbox{}\ \ \ \ \ \ \textcolor{ForestGreen}{int}\ node\ \textcolor{BrickRed}{=}\ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{top}}\textcolor{BrickRed}{().}to\textcolor{BrickRed}{;} \\
  41 \mbox{}\ \ \ \ \ \ \textcolor{ForestGreen}{int}\ dist\ \textcolor{BrickRed}{=}\ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{top}}\textcolor{BrickRed}{().}weight\textcolor{BrickRed}{;} \\
  42 \mbox{}\ \ \ \ \ \ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{pop}}\textcolor{BrickRed}{();} \\
  43 \mbox{} \\
  44 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}dist\ \textcolor{BrickRed}{$>$}\ d\textcolor{BrickRed}{[}node\textcolor{BrickRed}{])}\ \textbf{\textcolor{Blue}{continue}}\textcolor{BrickRed}{;} \\
  45 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}node\ \textcolor{BrickRed}{==}\ t\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{break}}\textcolor{BrickRed}{;} \\
  46 \mbox{} \\
  47 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}g\textcolor{BrickRed}{[}node\textcolor{BrickRed}{].}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{();}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  48 \mbox{}\ \ \ \ \ \ \ \ \textcolor{ForestGreen}{int}\ to\ \textcolor{BrickRed}{=}\ g\textcolor{BrickRed}{[}node\textcolor{BrickRed}{][}i\textcolor{BrickRed}{].}to\textcolor{BrickRed}{;} \\
  49 \mbox{}\ \ \ \ \ \ \ \ \textcolor{ForestGreen}{int}\ w$\_$extra\ \textcolor{BrickRed}{=}\ g\textcolor{BrickRed}{[}node\textcolor{BrickRed}{][}i\textcolor{BrickRed}{].}weight\textcolor{BrickRed}{;} \\
  50 \mbox{} \\
  51 \mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}dist\ \textcolor{BrickRed}{+}\ w$\_$extra\ \textcolor{BrickRed}{$<$}\ d\textcolor{BrickRed}{[}to\textcolor{BrickRed}{])}\textcolor{Red}{\{} \\
  52 \mbox{}\ \ \ \ \ \ \ \ \ \ d\textcolor{BrickRed}{[}to\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ dist\ \textcolor{BrickRed}{+}\ w$\_$extra\textcolor{BrickRed}{;} \\
  53 \mbox{}\ \ \ \ \ \ \ \ \ \ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{push}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{edge}}\textcolor{BrickRed}{(}to\textcolor{BrickRed}{,}\ d\textcolor{BrickRed}{[}to\textcolor{BrickRed}{]));} \\
  54 \mbox{}\ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  55 \mbox{}\ \ \ \ \ \ \textcolor{Red}{\}} \\
  56 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  57 \mbox{}\ \ \ \ \textbf{\textcolor{Black}{printf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}Case\ \#\%d:\ "{}}}\textcolor{BrickRed}{,}\ C\textcolor{BrickRed}{);} \\
  58 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}d\textcolor{BrickRed}{[}t\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{$<$}\ INT$\_$MAX\textcolor{BrickRed}{)}\ \textbf{\textcolor{Black}{printf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}\%d}}\texttt{\textcolor{CarnationPink}{\textbackslash{}n}}\texttt{\textcolor{Red}{"{}}}\textcolor{BrickRed}{,}\ d\textcolor{BrickRed}{[}t\textcolor{BrickRed}{]);} \\
  59 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{else}}\ \textbf{\textcolor{Black}{printf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}unreachable}}\texttt{\textcolor{CarnationPink}{\textbackslash{}n}}\texttt{\textcolor{Red}{"{}}}\textcolor{BrickRed}{);} \\
  60 \mbox{}\ \ \textcolor{Red}{\}} \\
  61 \mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  62 \mbox{}\textcolor{Red}{\}} \\
  63
  64 } \normalfont\normalsize